package algorthm.systemTraning.greedyAlgorithm;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @className: IPO
 * @Description:
 * @Author: wangyifei
 * @Date: 2024/4/20 10:41
 */
public class IPO {
    /**
     * 有 N 个项目，投入 k 后可获得 m 元利润，现在又 M 启动资金，只允许左 i 个项目，则最多可以拿到多少钱。
     */
    public static void main(String[] args) {
        List<Project> list = new ArrayList<>();
        list.add(new Project(2,4));
        list.add(new Project(4,2));
        list.add(new Project(6,7));
        list.add(new Project(3,1));
        int startMoney = 3 ;
        int cnt = 3 ;
        PriorityQueue<Project> small = new PriorityQueue<>(list.size(), new Comparator<Project>() {
            @Override
            public int compare(Project o1, Project o2) {
                return o1.money - o2.money;
            }
        });
        PriorityQueue<Project> big = new PriorityQueue<>(new Comparator<Project>() {
            @Override
            public int compare(Project o1, Project o2) {
                return o2.profile - o1.profile;
            }
        });
        small.addAll(list);
        for(int i = 0 ; i < cnt ; i++){
            while(!small.isEmpty() && small.peek().money <= startMoney){
                big.add(small.poll());
            }
            if(!big.isEmpty()){
                startMoney += big.poll().profile;
            }
            if(!big.isEmpty()){
                small.addAll(big);
                big.clear();
            }
        }
        System.out.println(startMoney);
    }
    public static class Project{
        public int money ;
        public int profile ;
        public Project(int m , int p){
           money = m ;
           profile = p ;
        }
    }
}
